<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>

</body>
<script>
    // lru
    // class Lru {
    //     constructor(size) {
    //         this.size = size
    //         this.container = []
    //     }
    //     // a,b,c,d,e

    //     // d,a,b,c,e
    //     setData(value) {
    //         let index = this.container.indexOf(value)
    //         if (index > 0) {
    //             this.container.splice(index, 1)
    //             this.container.unshift(value)
    //         } else {
    //             if (this.container.length >= this.size) {
    //                 this.container.splice(this.container.length - 1, 1)
    //             }
    //             this.container.unshift(value)
    //         }
    //         console.log('this.container:', this.container)
    //         return this.container
    //     }
    // }
    // let ins = new Lru(3)
    // ins.setData(1)
    // ins.setData(2)
    // ins.setData(3)
    // ins.setData(4)
    // ins.setData(5)


    // 数组版本
    // var LRUCache = function (capacity) {
    //     this.capacity = capacity;
    //     this.cache = [];
    // };

    // /**
    //  * @param {number} key
    //  * @return {number}
    //  */
    // LRUCache.prototype.get = function (key) {
    //     let index = this.cache.findIndex((item) => item.key === key);
    //     if (index === -1) {
    //         return -1;
    //     }
    //     // 删除此元素后插入到数组第一项
    //     let value = this.cache[index].value;
    //     this.cache.splice(index, 1);
    //     this.cache.unshift({
    //         key,
    //         value,
    //     });
    //     return value;
    // };

    // /**
    //  * @param {number} key
    //  * @param {number} value
    //  * @return {void}
    //  */
    // LRUCache.prototype.put = function (key, value) {
    //     let index = this.cache.findIndex((item) => item.key === key);
    //     // 想要插入的数据已经存在了，那么直接提升它就可以
    //     if (index > -1) {
    //         this.cache.splice(index, 1);
    //     } else if (this.cache.length >= this.capacity) {
    //         // 若已经到达最大限制，先淘汰一个最久没有使用的
    //         this.cache.pop();
    //     }
    //     this.cache.unshift({ key, value });
    // };

    // es6 map 版本
    // 利用了es6 map 的一些特殊性
    // var LRUCache = function (capacity) {
    //     this.cache = new Map();
    //     this.capacity = capacity;
    // };

    // LRUCache.prototype.get = function (key) {
    //     if (this.cache.has(key)) {
    //         // 存在即更新
    //         let temp = this.cache.get(key);
    //         this.cache.delete(key);
    //         this.cache.set(key, temp);
    //         return temp;
    //     }
    //     return -1;
    // };

    // LRUCache.prototype.put = function (key, value) {
    //     if (this.cache.has(key)) {
    //         // 存在即更新（删除后加入）
    //         this.cache.delete(key);
    //     } else if (this.cache.size >= this.capacity) {
    //         // 不存在即加入
    //         // 缓存超过最大值，则移除最近没有使用的
    //         this.cache.delete(this.cache.keys().next().value);
    //     }
    //     this.cache.set(key, value);
    // };


    // let ins = new LRUCache(3)
    // ins.put('a', '1')
    // ins.put('b', '2')
    // ins.put('c', '3')
    // ins.put('d', '4')
    // ins.put('e', '5')


    // 回文字符串：是一个正读和反读都一样的字符串。
    // abcdefg
    function isLoopStr(str) {
        if (typeof str !== 'string' && !str.length) return
        let flag = true
        for (let i = 0; i < Math.floor(str.length / 2); i++) {
            if (str[i] !== str[str.length - 1 - i]) {
                flag = false
                break
            }
        }
        return flag
    }

    // 反转链表
    // a -> b -> c
    // a <- b <- c
    var reverseList = function (head) {
        let prev = null;
        let curr = head;
        while (curr !== null) {
            let cnext = curr.next;
            curr.next = prev === null ? null : prev
            prev = curr;
            curr = cnext;
        }
        return prev
    };

    // 链表中环的检测
    // a -> b -> c -> a
    function isCircle(head) {
        let arr = [], isCircle = false
        while (head.next && !isCircle) {
            if (arr.includes(head.value)) {
                isCircle = true
            }
            arr.push(head.value)
        }
        return isCircle
    }

    let obj1 = {
        value: 1,
        next: {
            value: 3,
            next: {
                value: 4
            }
        }
    }

    let obj2 = {
        value: 2,
        next: {
            value: 5,
            next: {
                value: 8
            }
        }
    }
    // 有序链表合并
    // 1 -> 3 -> 4
    // 2 -> 5 -> 8
    function ListNode(val) {
        this.val = val;
        this.next = null;
    }

    var mergeTwoLists_2 = function (l1, l2) {
        //不需要特意判断l1、l2为空
        let head = new ListNode(0); //创建一个含有头结点的链表，随便指一个值，其第二个节点开始保存结果
        let pre = head; //遍历结果的指针，总指向最后一个节点
        while (l2 && l1) { //都不为null（空）时
            if (l1.value > l2.value) { //l1对应的值大于l2
                pre.next = l2;
                l2 = l2.next; //l2往后遍历
            } else { //小于或者等于
                pre.next = l1;
                l1 = l1.next;
            }
            pre = pre.next;  //pre更新
        }
        //将没有比较过的l1或者l2添加到尾部
        pre.next = l1 ? l1 : l2;//初始的时候不需要特意判断l1、l2为空，因为有一个为空会跳过while循环
        return head.next; //头结点是新建的节点，返回时，不需要该点
    };


    console.log('合并有序链表:', mergeTwoLists_2(obj1, obj2))

    // 删除链表倒数第n个节点
    // obj1
    function deleteNode(index){
        
    }
    // 求链表的中间节点

</script>

</html>